package leetcode.editor.cn.dsa02_linkedlist;
//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

public class AddTwoNumbers2_3 {
    public static void main(String[] args) {
        Solution solution=new AddTwoNumbers2_3().new Solution();
        // 测试用例
        int[] arr1 = {2, 4, 7};
        int[] arr2 = {5, 6, 4, 9};
        ListNode l1 = new AddTwoNumbers2_3().new ListNode();
        ListNode l2 = new AddTwoNumbers2_3().new ListNode();
        ListNode l1Cur = l1;
        ListNode l2Cur = l2;
        for (int i = 0; i < arr1.length; i++) {
            ListNode node1 = new AddTwoNumbers2_3().new ListNode(arr1[i]);
            l1Cur.next = node1;
            l1Cur = node1;
        }
        for (int i = 0; i < arr2.length; i++) {
            ListNode node2 = new AddTwoNumbers2_3().new ListNode(arr2[i]);
            l2Cur.next = node2;
            l2Cur = node2;
        }
        ListNode result = solution.addTwoNumbers(l1.next, l2.next);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val; // 数据域
        ListNode next; // 指针域，指向下一个节点
        ListNode() {}
        ListNode(int val) { this.val = val; }
    }
    class Solution {
        /**
         * 最优解：数学思维解法
         * 1.遍历两个链表
         * 2.对应位置的节点数值相加
         * 3.将计算结果插入新链表尾部
         * 大于10，则进位，将进位加到下个节点
         *
         * 边界问题
         *     两个链表边界： next==null
         * 细节问题
         *     两个链表长度不一致，短链表高位视为0
         *     链表最高位发生进位，结果链表需要增加一个节点存放进位数字
         *
         * @param l1
         * @param l2
         * @return
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode p1 = l1, p2 = l2; // 原链表的两个遍历指针
            ListNode resultHead = new ListNode(-1); // 结果链表的头结点head
            ListNode cur = resultHead; // 结果链表的遍历指针，代表当前操作的节点
            int carry = 0; // 记录进位
            // 1.遍历两个链表
            while (p1 != null || p2 != null) { // 以长链表为准
                // 获取当前节点的值：链表较短，已无节点，取0
                int x = p1 == null ? 0 : p1.val;
                int y = p2 == null ? 0 : p2.val;
                // 2.对应位置的节点数值相加
                int sum = x + y + carry;
                carry = sum / 10; // 得到本次运算的进位
                int num = sum % 10; // 存放到新链表节点中的数值
                // 3.将计算结果插入新链表尾部
                cur.next = new ListNode(num);
                cur = cur.next;
                p1 = p1 == null ? p1 : p1.next;
                p2 = p2 == null ? p2 : p2.next;
            }
            if (carry != 0) { // 最高位发生进位
                cur.next = new ListNode(carry);
            }
            return resultHead.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}